Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary (...) computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way. (shrink)

We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.

It is shown that there exists a low2 Harrington non-splitting base-that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if $0' = x \vee y$ , then either $0' = x \vee a$ or $0' = y \vee a$ . Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the $low_{2}-ness$ requirements to be satisfied, and the proof given involves new techniques with potentially wider application.

Turing’s paper on computable numbers has played its role in underpinning different perspectives on the world of information. On the one hand, it encourages a digital ontology, with a perceived flatness of computational structure comprehensively hosting causality at the physical level and beyond. On the other, it can give an insight into the way in which higher order information arises and leads to loss of computational control—while demonstrating how the control can be re-established, in special circumstances, via suitable type reductions. (...) We examine the classical computational framework more closely than is usual, drawing out lessons for the wider application of information–theoretical approaches to characterizing the real world. The problem which arises across a range of contexts is the characterizing of the balance of power between the complexity of informational structure and the means available to bring this information back into the computational fold. We proceed via appropriate mathematical modelling to a more coherent view of the computational structure of information, relevant to a wide spectrum of areas of investigation. (shrink)

We say that a computably enumerable (c.e.) degree b is a Lachlan nonsplitting base (LNB), if there is a computably enumerable degree a such that a > b, and for any c.e. degrees w,v ≤ a, if a ≤ w or; v or; b then either a ≤ w or; b or a ≤ v or; b. In this paper we investigate the relationship between bounding and nonbounding of Lachlan nonsplitting bases and the high /low hierarchy. We prove that there (...) is a non-Low2 c.e. degree which bounds no Lachlan nonsplitting base. (shrink)

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, ${{\bf 0' = b \lor x}}$ if and only if (...) ${{\bf 0' = a \lor x}}$ . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. (shrink)

A proof is given that 0′ is definable in the structure of the degrees of unsolvability. This answers a long-standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.

We show that every nonzero Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, e-degrees which bound no minimal pair.

In this paper we examine a class of pairs of recursively enumerable degrees, which is related to the Slaman-Soare Phenomenon.

We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair.

We show that for any computably enumerable set A and any equation image set L, if L is low and equation image, then there is a c.e. splitting equation image such that equation image. In Particular, if L is low and n-c.e., then equation image is n-c.e. and hence there is no low maximal n-c.e. degree.

We prove that there exists a noncappable enumeration degree strictly below 0' e.

We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees.

We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering, such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.

Foucault is often thought to have a great deal to say about the history of madness and sexuality, but little in terms of a general analysis of government and the state.; This volume draws on Foucault's own research to challenge this view, demonstrating the central importance of his work for the study of contemporary politics.; It focuses on liberalism and neo- liberalism, questioning the conceptual opposition of freedom/constraint, state/market and public/private that inform liberal thought.

Previous work demonstrates that music with more surprising chords tends to be perceived as more enjoyable than music with more conventional harmonic structures. In that work, harmonic surprise was computed based upon a static distribution of chords. This would assume that harmonic surprise is constant over time, and the effect of harmonic surprise on music preference is similarly static. In this study we assess that assumption and establish that the relationship between harmonic surprise and music preference is not constant as (...) time goes on. Analyses of harmonic surprise and preference from 1958 to 1991 showed increased harmonic surprise over time, and that this increase was significantly more pronounced in preferred songs. Separate analyses showed similar increases over the years from 2000 to 2019. As such, these findings provide evidence that the human perception of tonality is influenced by exposure. Baseline harmonic expectations that were developed through listening to the music of “yesterday” are violated in the music of “today,” leading to preference. Then, once the music of “today” provides the baseline expectations for the music of “tomorrow,” more pronounced violations—and with them, higher harmonic surprise values—become associated with preference formation. We call this phenomenon the “Inflationary-Surprise Hypothesis.” Support for this hypothesis could impact the understanding of how the perception of tonality, and other statistical regularities, are developed in the human brain. (shrink)

We describe a strategy that is being used for the horizontal integration of warfighter intelligence data within the framework of the US Army’s Distributed Common Ground System Standard Cloud (DSC) initiative. The strategy rests on the development of a set of ontologies that are being incrementally applied to bring about what we call the ‘semantic enhancement’ of data models used within each intelligence discipline. We show how the strategy can help to overcome familiar tendencies to stovepiping of intelligence data, and (...) describe how it can be applied in an agile fashion to new data resources in ways that address immediate needs of intelligence analysts. (shrink)

Despite the enormous influence of Michel Foucault in gender studies, social theory, and cultural studies, his work has been relatively neglected in the study of politics. Although he never published a book on the state, in the late 1970s Foucault examined the technologies of power used to regulate society and the ingenious recasting of power and agency that he saw as both consequence and condition of their operation. These twelve essays provide a critical introduction to Foucault's work on politics, exploring (...) its relevance to past and current thinking about liberal and neo-liberal forms of government. Moving away from the great texts of liberal political philosophy, this book looks closely at the technical means with which the ideals of liberal political rationalities have been put into practice in such areas as schools, welfare, and the insurance industry. This fresh approach to one of the seminal thinkers of the twentieth century is essential reading for anyone interested in social and cultural theory, sociology, and politics. (shrink)

Here we present what we believe is a novel account of what languages are, along with an axiomatically rich representation of languages and language-related data that is based on this account. We propose an account of languages as aggregates of dispositions distributed across aggregates of persons, and in doing so we address linguistic competences and the processes that realize them. This paves the way for representing additional types of language-related entities. Like demographic data of other sorts, data about languages may (...) be of use to researchers in a number of areas, including biomedical research. Data on the languages used in clinical encounters are typically included in medical records, and capture an important factor in patient-provider interactions. Like many types of patient and demographic data, data on a person’s preferred and primary languages are organized in different ways by different systems. This can be a barrier to data integration. We believe that a robust framework for representing language in general and preferred and primary language in particular – which has been lacking in ontologies thus far – can promote more successful integration of language-related data from disparate data sources. (shrink)

Foucault is often thought to have a great deal to say about the history of madness and sexuality, but little in terms of a general analysis of government and the state.; This volume draws on Foucault's own research to challenge this view, demonstrating the central importance of his work for the study of contemporary politics.; It focuses on liberalism and neo- liberalism, questioning the conceptual opposition of freedom/constraint, state/market and public/private that inform liberal thought.

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

The significance of teaching to the evolution of human culture is under debate. We contribute to the discussion by using a quantitative, cross-cultural comparative approach to investigate the role of teaching in the lives of children in two small-scale societies: Aka foragers and Ngandu farmers of the Central African Republic. Focal follows with behavior coding were used to record social learning experiences of children aged 4 to 16 during daily life. “Teaching” was coded based on a functional definition from evolutionary (...) biology. Frequencies, contexts, and subtypes of teaching as well as the identity of teachers were analyzed. Teaching was rare compared to observational learning, although both forms of social learning were negatively correlated with age. Children received teaching from a variety of individuals, and they also engaged in teaching. Several teaching types were observed, including instruction, negative feedback, and commands. Statistical differences in the distribution of teaching types and the identity of teachers corresponded with contrasting forager vs. farmer foundational cultural schema. For example, Aka children received less instruction, which empirically limits autonomous learning, and were as likely to receive instruction and negative feedback from other children as they were from adults. Commands, however, exhibited a different pattern suggesting a more complex role for this teaching type. Although consistent with claims that teaching is relatively rare in small-scale societies, this evidence supports the conclusion that teaching is a universal, early emerging cognitive ability in humans. However, culture structures the nature of teaching. (shrink)

We show that there exists a properly Σ2 minimal degree b, and moreover that b can be chosen to join with 0′ to 0″ – so that b is a 0″ complement for every degree a such that 0′ ≤ a < 0″.

The evolution of the human brain has resulted in the emergence of higher-order cognitive abilities, such as reasoning, planning and social awareness. Although there has been a concomitant increase in brain size and complexity, and component diversification, we argue that RNA regulation of epigenetic processes, RNA editing, and the controlled mobilization of transposable elements have provided the major substrates for cognitive advance. We also suggest that these expanded capacities and flexibilities have led to the collateral emergence of psychiatric fragilities and (...) conditions. (shrink)

We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover.

Most of what we know about teaching comes from research among people living in large, politically and economically stratified societies with formal education systems and highly specialized roles with a global market economy. In this paper, we review and synthesize research on teaching among contemporary hunter-gatherer societies. The hunter-gatherer lifeway is the oldest humanity has known and is more representative of the circumstances under which teaching evolved and was utilized most often throughout human history. Research among contemporary hunter-gatherers also illustrates (...) a complex pattern of teaching that is both consistent with and distinct from teaching in other small- and large-scale societies with different subsistence practices and cultural forms. In particular, we find that the cultural emphasis on individual autonomy and socio-political egalitarianism among hunter-gatherers differently shapes how teaching occurs. For example, teaching clearly exists among hunter-gatherers and appears in many forms, including institutionalized instruction in valued cultural and technical skills. However, teaching tends to be less common in hunter-gatherer societies because people live in small, intimate egalitarian, groups that support each other’s learning in a variety of ways without teaching. Furthermore, foundational cultural schemas of autonomy and egalitarianism impact the nature of teaching. For example, adults and older children limit their interventions, permitting autonomous learning, and, when they occur, teaching episodes are generally brief, subtle, indirect, and situated in a present activity. We discuss the implications of this research in terms of discussions of the evolution of human cognition and the co-evolution of teaching and culture through the process of cultural niche construction. (shrink)

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)

In this presentation, I set out to clarify, first, what the Jewish tradition finds in the life of Abraham that accords special value to rational reflection and even philosophical inquiry. Second, I examine a specific example of how this characterization and valuation of Abraham plays out within the tradition of medieval Jewish scholastic theology in tenth-century Baghdad by examining Sa‘adia Gaon’s famous “Argument from Time” to establish both the creation of the universe in time and, by implication, the existence of (...) a Creator God. From there, I show how he draws upon the work of John Philoponus in constructing his argument. Third, I present and analyze a well-known philosophical parable that Moses Maimonides, representing the tradition of religious philosophy, introduces early on in The Guide of the Perplexed. This parable deals in a subtle and suggestive way with the possibilities and limitations of trying to free people from perplexity and guide them towards wisdom. It owes a great deal to the work of Abū Bakr ibn al-’ Ṣā’igh, otherwise known as Ibn Bājjah. I conclude with a number of observations on how Maimonides may have interpreted his sources so as to develop his distinctive view of God and how the pursuit of philosophical wisdom is compatible with the love of God. (shrink)

In this presentation, I set out to clarify, first, what the Jewish tradition finds in the life of Abraham that accords special value to rational reflection and even philosophical inquiry. Second, I examine a specific example of how this characterization and valuation of Abraham plays out within the tradition of medieval Jewish scholastic theology in tenth-century Baghdad by examining Sa‘adia Gaon’s famous “Argument from Time” to establish both the creation of the universe in time and, by implication, the existence of (...) a Creator God. From there, I show how he draws upon the work of John Philoponus in constructing his argument. Third, I present and analyze a well-known philosophical parable that Moses Maimonides, representing the tradition of religious philosophy, introduces early on in The Guide of the Perplexed. This parable deals in a subtle and suggestive way with the possibilities and limitations of trying to free people from perplexity and guide them towards wisdom. It owes a great deal to the work of Abū Bakr ibn al-’ Ṣā’igh, otherwise known as Ibn Bājjah. I conclude with a number of observations on how Maimonides may have interpreted his sources so as to develop his distinctive view of God and how the pursuit of philosophical wisdom is compatible with the love of God. (shrink)